package com.michael.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 快速排序
 */
public class Quicksort {
    public static <T extends Comparable> void sort(T[] data, int start, int end) {
        if (start >= end)
            return;
        T base = data[start];
        int baseIndex = start;
        int left = start + 1, right = end;
        while (left < right) {
            while (left < right && data[right].compareTo(base) >= 0) {
                right--;
            }
            data[baseIndex] = data[right];
            baseIndex = right;

            while (left < right && data[left].compareTo(base) <= 0) {
                left++;
            }
            data[baseIndex] = data[left];
            baseIndex = left;
        }
        data[baseIndex] = base;
        if (baseIndex > start) sort(data, start, baseIndex - 1);
        if (baseIndex < end) sort(data, baseIndex + 1, end);
    }

    public static <T extends Comparable> List<T> sort(List<T> data) {
        List<T> result = new ArrayList<>();
        if (data.size() == 0) {
            return result;
        }
        T base = data.get(0);
        List<T> left = new ArrayList<>();
        List<T> right = new ArrayList<>();
        for (int i = 1; i < data.size(); i++) {
            if (data.get(i).compareTo(base) >= 0) {
                right.add(data.get(i));
            } else {
                left.add(data.get(i));
            }
        }
        left = sort(left);
        right = sort(right);
        left.forEach(result::add);
        result.add(base);
        right.forEach(result::add);
        return result;
    }

    public static int[] qsort(int arr[], int start, int end) {
        int pivot = arr[start];
        int left = start;
        int right = end;
        while (left < right) {
            while ((left < right) && (arr[right] > pivot)) {
                //找出低于基准值的角标
                right--;
            }
            while ((left < right) && (arr[left] < pivot)) {
                //找出高于基准值的角标
                left++;
            }
            if ((arr[left] == arr[right]) && (left < right)) {
                //只有都等于基准值的，直接向右偏移
                left++;
            } else {
                //交换位置
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //left==right,也就是基准值所在的位置
        if (left - 1 > start) arr = qsort(arr, start, left - 1);
        if (right + 1 < end) arr = qsort(arr, right + 1, end);
        return (arr);
    }

}
